Complex telecommunication networks, such as telephone networks, are configured using a plurality of nodes (vertices) that are interconnected via communication lines (edges). For example, a Synchronous Optical Network (SONET) used as an Interoffice Facility (IOF) can have dozens or even hundreds of interconnected nodes.
The interconnection among the nodes is a function of the costs for each connection (edge cost) and the expected or measured communications traffic among the various nodes. The cost of an edge is based on a variety of functional factors familiar to one of ordinary skill in the art, such as the communication medium used to interconnect the nodes and the distance between the nodes. It is often desirable to provide a redundant path of minimum cost among a selected subset of the network nodes that are in communication. Selection of the subset of nodes is based on a variety of functional factors familiar to one of ordinary skill in the art, such as measured or expected volume of communication traffic between the nodes.
One way to provide a redundant path through the subset of nodes is to provide a "ring" or circuit through the selected subset of the nodes. The ring consists of edges of the network forming a closed path that does not pass through the same node twice. Consequently, for any two nodes on the ring, there are two separate communication paths. One path is in the "clockwise" direction on the ring and the other path is in the "counterclockwise" direction on the ring.
For a given subset of nodes, it is desirable to find the lowest cost ring passing through the subset of nodes. That is, assuming each edge has a particular cost, it is desirable to find the set of edges having the lowest total cost that passes through the subset of nodes. In some instances it may be possible to simply try all of the possible combinations of interconnections. However, for complex networks, this method is ineffective because of the large number of computations involved. Other methods for determining the lowest cost ring exist, but these methods also are computationally cumbersome and often take an unacceptable amount of time to execute.
It is desirable, therefore, to provide a communications network ring router that overcomes the deficiencies of known systems.